package net.tp.algo.sort;

/**
 * User: Trung
 * Date: 4/27/13
 * Time: 8:30 AM
 */
public class StringLsdRadixSort {

    public static final int R = 256;

    public static void sort(String[] data, int strLen, boolean asc) {

        int N = data.length;
        String[] aux = new String[N];
        String[] source = data;
        String[] target = aux;

        for (int s = strLen - 1; s >= 0; s--) {
            int[] counts = new int[R];

            for (String text : source) {
                counts[charAt(text, s)]++;
            }

            if (asc) {
                for (int i = 1; i < R; i++) {
                    counts[i] += counts[i-1];
                }
            }
            else {
                for (int i = R-2; i >= 0; i--) {
                    counts[i] += counts[i+1];
                }
            }

            for (int i = N - 1; i >= 0; i--) {
                target[--counts[charAt(source[i], s)]] = source[i];
            }

            String[] tmp = source; source = target; target = tmp;
        }

        if (source != data) {
            for (int i = 0; i < N; i++) {
                data[i] = source[i];
            }
        }
    }

    /**
     * simulate fixed length string
     * @param text
     * @param i
     * @return
     */
    private static char charAt(String text, int i) {
        return i < text.length() ? text.charAt(i) : (char)0;
    }


}
